package LeetCode_Section;

public class DetermineHuiWen {
    public static class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }
    public static boolean chkPalindrome(ListNode A) {
        //思路：
        //1、先使用快慢指针 找出中间节点
        //2、以中间节点为起始位置 往后的链表陆续反转
        //3、前后双指针同时走 判断是否相同 （考虑元素的奇偶数）
        /*
        if (A == null) {
            return false;
        }

        ListNode fast = A;
        ListNode slow = A;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode cur = slow.next;

        //从中间节点之后开始翻转
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }

        while (A != slow) {
            if (A.val != slow.val) {
                return false;
            }
            //考虑是元素个数是偶数的情况
            if (A.next == slow) {
                return true;
            }
            A = A.next;
            slow = slow.next;
        }
        return true;
*/

        // byMyself -- 问题代解决 8.15
        ListNode B = A;
        myReverse(B);
        ListNode headA = A;
        ListNode headB = B;

        while (headA == null || headB == null) {
            if (headA.val != headB.val) {
                return false;
            }else {
                headA = headA.next;
                headB = headB.next;
            }
        }
        return true;
    }

    public static ListNode myReverse(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;

        if (head == null || head.next == null) {
            return head;
        }

        while (cur != null) {
            ListNode last = cur.next;
            cur.next = pre;
            pre = cur;
            cur = last;
        }
        return pre;
    }


    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = null;

        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val+"->");
            cur = cur.next;
        }
        System.out.println("null");
        ListNode newHead = head;
        System.out.println("反转⬇️");
        cur = myReverse(newHead);
        while (cur != null) {
            System.out.print(cur.val+"->");
            cur = cur.next;
        }
        System.out.println("null");
        System.out.println();
        System.out.println(chkPalindrome(head));

    }
}
